Nimで自作インタプリタ② Pratt Parserを実装した
2019/2/7
Lexerの次にParserを作り始めたのですが、一段落したので軽く記事にまとめます。
スライド
勉強会でスライドを作って発表しました。
内容はこのブログ記事の方が詳細です。
概要
前回に引き続き、「『Go言語でつくるインタプリタ』」本をNimで書き直しながら進めています。前回のLexerの記事から随分と時間がかかったのは、Nimのことをあまり知らない状態でGoの書き直しをしたのもあり、主にインターフェースの周りですごく詰まったからです。 この辺の苦労話はこの記事の最後の方に書きます。
記事の前半では、Parserとはそもそもなんなのかや、Pratt Parserの仕組みなどについて簡単に紹介します。
リポジトリは以下です。
参考
ParserはToken列からASTを作るやつ
Parserは日本語では「構文解析器」といいます。
ParserはLexerが作ったToken列を受け取ってASTを作ります。
簡単な手順としては以下のような感じです。
まず、入力された文字列を、Lexerが、文章の最小構成要素であるTokenに分解してくれます。
次に、Parserはそこで受け取ったTokenを読んで、その種類や内容を見ながら抽象構文木(AST)を作っていきます。
「構文解析」自体は、プログラミングだけの話ではなく、例えば自然言語処理などの界隈でも出てくるワードです。
ASTとは
AST、Abstract Syntax Tree。
日本語では「抽象構文木」。
ASTというのは、その名の通り抽象的な構文木のことです。
「抽象的」なので、空白や行末セミコロン、括弧などの、意味は同じだけど表現が異なるだけのものが省かれています。
少し横道に逸れますが、ASTは言語処理系以外のところでも使われています。
例えば、メタプログラミング、コード整形、DIを使ったデバッグやテストや、ドキュメントの自動生成などです。
言語ごとにASTを解析したり、visualizeするツールをいくつか見つけたので載せておきます。
いくつかの言語のASTを出力してくれる
Pythonの
Goの
JSの
js周辺(というかBabel周辺)のツールについては以下の本に詳しく書かれていました。
babylonなどを使ってjsのコードをASTにし、ちょっといじって、再びjsコードに変換するツールを作っていく本です。(まだ読んでる途中)
参考
Goなら以下の記事などが参考になります。
参考
具体例
構文解析の話に戻ります。
先ほどの説明だけではわかりにくいので実際の出力を見てみます。
ここでは、let hoge = 1 + 2 * 3 / 4 + 5 - 6; という文字列(コードじゃなくてただの文字列！)を解析してみます。
式と文と式文
今回の例のlet hoge = 1 + 2 * 3 / 4 + 5 - 6;のように変数に値を束縛する式を、ここでは「let文」と呼びますが、let文は以下のような構造になっています。
let <identifier> = <expression>
identifierは変数名などを表し、expressionは式を表します。
「式(expression)」というのは、値を出力するもののことで、例えば、42だったり、"foo"だったりが該当します。
式の他に、「文(statement)」というものもあり、これは上記のlet hoge = piyopiyoだったり、return fugaだったり、それ自体が値を生成しないものを指します。
また、「式文(expression statement)」というのもあります。
これは一つの式だけからなる文のことです。
例えば、x + 2 などです。
Lexerの出力
まずは先ほどのlet文の文字列である
let hoge = 1 + 2 * 3 / 4 + 5 - 6;からTokenを作ってみます。
ここでは、前回の記事のときに作ったLexerを使います。
code:nim
var
input = """let hoge = 1 + 2 * 3 / 4 + 5 - 6;"""
l = newLexer(input)
for i in 1..15:
var tok = l.nextToken()
echo repr tok
出力は(ちょっと整形してますが)こんな感じです。
さきほどの文字列がTokenに分けられているのがわかります。
code:Tokens
作られるASTオブジェクト
次に、今回作ったParserで構文解析してみると、(ちょっと整形していますが)以下のような構造体が作られます。
code:ast
Token: {
Type: 'LET',
Literal: 'let'
},
Let: {
Token: {
Type: 'IDENT',
Literal: 'hoge'
},
IdentValue: 'hoge'
},
LetValue: {
Left: {
Left: {
Token: {
Type: 'INT',
Literal: '1'
},
IntValue: 1
},
Operator: '+',
Right: {
Left: {
Left: {
Token: {
Type: 'INT',
Literal: '2'
},
IntValue: 2
},
Operator: '*',
Right: {
Token: {
Type: 'INT',
Literal: '3'
},
IntValue: 3
}
},
Operator: '/',
Right: {
Token: {
Type: 'INT',
Literal: '4'
},
IntValue: 4
}
}
},
Operator: '+',
InRight: {
Left: {
Token: {
Type: 'INT',
Literal: '5'
},
IntValue: 5
},
Operator: '*',
Right: {
Token: {
Type: 'INT',
Literal: '6'
},
IntValue: 6
}
}
}
少し大きいので、わかりにくいですが、雑に図にしてみると以下のような構造になっています。
https://gyazo.com/5b2c1d42efd8d7020458ac2f84d6f2ab
実際に動いている様子
parserが作ったASTをを元に、括弧がつけられ、最終的に以下のように出力されます。
let hoge = (((1 + ((2 * 3) / 4)) + 5) - 6);
入力の括弧と記号の優先順位をちゃんと認識しながら抽象構文木が作られているのがわかります。
まだ評価機能が実装されていないので、計算式の結果を求めるのではなく、入力を見て正しく括弧を付けるだけのものです。
Pratt構文解析器
構文解析器にもいろんな種類がありますが、今回は1973年にVaughan Pratt氏の論文で発表されたPratt構文解析器という手法で実装しています。
Pratt構文解析器がどんなものかというと論文の中では以下のように紹介されています。
very simple to understand, trivial to implement, easy to use, extremely efficient in practice if not in theory, yet flexible enough to meet most reasonable syntactic needs of users in both categories (i) and (ii) above.
つまり、
シンプルで理解しやすい
実装が簡単
使いやすい
理論上はもちろん実用上もとても効率的
利用者の殆どの合理的な公文に耐えられるほど柔軟
参考
Pratt Parserは下向き演算子順位解析を用いたもので、手書きでParserを書く時に有効な手法のようです。
普通、自作言語を作る場合はyaccなどのパーサジェネレータを使って、文法のみを定義しますが、今回は1からparserを実装しています。
参考
パーサジェネレータというのは、バッカス・ナウア記法(BNF)を用いて文法などを記述し、parserを自動生成するプログラムのことです。
が、僕はそもそもパーサージェネレータの方を触ったことがないので、いまいちイメージが掴めていません・・。
Parserの種類
構文解析器は大きく分けて「トップダウン構文解析器」と「ボトムアップ構文解析器」に分けられます。
両方共にいくつか種類がありまして、例えば前者では「再帰下降構文解析」や「パックラット構文解析」などがあり、Pratt構文解析器はこの再帰下降構文解析に当たります。
Wikipediaに載っていたものを以下に掲載します。
トップダウン構文解析
再帰下降構文解析←PrattParserはこれ
LL法
末尾再帰構文解析
パックラット構文解析
ボトムアップ構文解析器
LR法
SLR法
LALR法
CLR法
GLR法
アーリー法
CYK法
思ってたより沢山の種類があって、圧倒されてしまいました。
一つ一つを知るのはまた別の機会にします・・。
興味がある方はwikiなどを参考にしてみてください。
参考
これも調べてる時に見つけたものですが、いくつかの種類の構文解析のアルゴリズムがビジュアル的にとてもわかりやすくまとめられているスライドを見つけたので、載せておきます。
Pratt Parserも載ってます。
参考
Pratt Parserのアルゴリズム
先ほどの例とコードの一部を切り取って、実際にどのように動いて木を作っていくのかを確認していきます。
例として先ほどの例の図のツリーの一部をパースする処理を順を追って見ていきます。
「2*3/4」という文字列から以下のようなツリーを作ります。
https://gyazo.com/48375c9629bab881291cd5b99b79e357
つまり、以下のような構造を持ったオブジェクトを作っていくことになります。
https://gyazo.com/2ec9077e0aa2d0a39a39902857efe2a1
ParserはLexerが作ったTokenを一つずつ見ていき、順に処理をしていきます。
今回の実装では、今見てるTokenをcurToken、その次のTokenをpeekTokenと呼び、Parser Objectのプロパティとして持っています。
これを処理とともに進めていくことで解析していきます。
https://gyazo.com/6f779f8a0d78ffdd7626ca96d01d2a67
「2 * 3」のツリーを作る
1.式か式文かを判断する
まず最初にcurTokenは2を指しています。
図の左下は関数のコールスタックになります。
https://gyazo.com/e3b67c8b975b270338deb84bb2029415
長くなるので、重要じゃない部分は省きます。
最初に呼び出されるparseStatement()は、curTokenを見て3つに分類して、それぞれの処理を行います。
今はcurTokenが2なので、ここでは一番下の、式文をparseする関数を呼び出します。
https://gyazo.com/678bc19e47a521b389223c2426975bea
2."2"をオブジェクトに保存する
次にparseExpression()が呼び出されます。
これがだいぶ重要な処理で、再帰的に呼び出される関数になります。
この中でさらに数値をparseする関数が呼び出され、2の部分のオブジェクトを返し、leftに代入します。
https://gyazo.com/b93395de3863ebda5ad8a414b459dfcd
2が作られました。
https://gyazo.com/af55d71321b38de397abf4a0f9d2e5f8
これを持った状態でwhileループに来ます。
ここの条件式がめっちゃ重要なので、あとで説明します。
ここでは条件を満たし、ループの中に入ります。
3.whileループの中に入る
ループの中では、peekTokenを見て次の処理を実行します。
ここでは、peekTokenは*です。
https://gyazo.com/8e69074329ce46b0b69b9df503b18bc9
https://gyazo.com/3e244212a6c89884cee50283562ae3a0
この中でnextToken()が呼ばれているので、見ているTokenを一つずらして次の処理に移ります。
4."*"をオブジェクトに保存する
この辺からPratt Parserの真髄に入っていきます。
*をオブジェクトに保存します。(上の矢印)
https://gyazo.com/180e696f356557b1b485f118b33d2449
https://gyazo.com/824efd9606af2e7139ee13536f64c34c
そして、Tokenを進め、さらに、parseExpression()を呼びます。
このparseExpression()は、図の右下のコールスタックの赤色のやつです。
つまりここで、再帰されたのです。
5.parseExpression 再び
今は、再帰呼び出しされたparseExpression()の中にいます。
さっきと同じように3をparseしてオブジェクトに保存します。
https://gyazo.com/42ba0aa4e0bd6674f0d2a53c3d19a7ad
先ほどとの違いは、whileループには入らない点です。
そのまま3を返します。
https://gyazo.com/e76799cb43e7935fd0e8a95d61f635e5
6.1個めのparseExpressionに戻ってきた
これで、2*3の部分が完成しました。
いやぁ、長いですね。まだ半分です。
https://gyazo.com/9a131271e929a22e61501b87cecc8177
もう忘れているかもしれませんが、今は一度目に呼び出されたparseExpression()のwhileループの中でした。
ここで、再びwhileループの一番上に戻ります。
ここでも、条件を満たすので、まだ抜けられません
https://gyazo.com/f70237e176f20cdfdb4253b1d0552f78
早く/4の部分をやってしまいたいですが、一旦このwhileループの条件の部分を確認します。
Tokenの優先順位つけ
実はこの部分がPratt Parserで最も大事な部分になります。
"+"、"("、"="など、コードの中では沢山の記号が出てきますが、これらの記号は数値などとの結びつきの優先度が異なります。
例えば、「1 + 2 * 3」という入力が合った時に、「(1 + 2) * 3」とするか、「1 + (2 * 3)」とするかで、答えが異なってきます。
これは、"+"よりも"*"の方が優先度が高いと定義されているので、後者のようにツリーが作られます。
今回の実装では、以下の列挙型でTokenの優先順位を決めています。
https://gyazo.com/32d0aace763ba0c9f64230287789e8c6
Nimも他の言語の列挙型と同じく、下に行くほど大きな数値が与えられます。
つまり、「Sum < Product」を評価するとtrueが返ります。
while文の条件式
さきほど何度かスルーしたwhile文の条件式を見てみます。
code:nim
while precedence < self.peekPrecedence() and not self.peekTokenIs(SEMICOLON):
hogehoge...
ここはandで２つの条件を判定しています。
１つ目は引数で得た優先順位とpeekTokenの優先順位を比較しています。
２つ目は単純に、peekTokenがセミコロンかどうかを見ています。
重要なのは１つ目の方で、ここで先ほどの列挙型を用いて定義した優先順位が使われるわけです。
記号同士の優先順位の強さを見て、周りの数字などがどちらに結びつくかを決定します。
「1 + 2 * 3」という入力で、「2」は両隣に「+」と「*」がいますが、結びつきの強さは「+」<「*」なので、「*」と結びつくことになります。
https://gyazo.com/61dd8c31d1f1ddcdb6f27f3389df7878
whileループの条件式の話に戻すと、引数で受け取った優先順位より、peekTokenの優先順位のほうが大きい場合に、ループの中に入ります。
続き 「/ 4」の部分を作る
さっきの続きです。やってることは同じです。
7.whileの中
whileの中でpeekTokenを見て、「/」の部分が実行されます。
https://gyazo.com/6a171e1bd456b29bada1319eb7ead73d
見てるTokenを進め、「/」を作ります。
https://gyazo.com/87fd752dcca4f08accad03f8bcc8c3de
https://gyazo.com/228966f1511c4c3306c4ab7bb8162279
8.parseExpresson 再び再び
https://gyazo.com/d3dd114efb574cd271f3361b47656946
再びparseExpressionを呼び出して最後の3をparseします。
この中では、while文の二つ目の条件、「次のTokenがセミコロンではない」を満たさないので、ループに入りません。
https://gyazo.com/db39a2fa2694cd73aa4fa87a10b040cc
9.完成
最後に今まで作ってきた、「2*3」と「/」と「4」をガッチャンコします。
https://gyazo.com/d22a3b13bc3f092cac20a3fc67d08c64
こうしてやっと、「2 * 3 / 4」をパースしてASTを作り終えることができました。
https://gyazo.com/c8f3d7232e4c97c7ce4f323a1554cbd8
こんな感じで進めていきます。
再帰があるので解説が複雑になってしまいました。
Pratt Parserの解説記事
PythonとJSを用いた解説記事があったので載せておきます。
Pythonを用いた解説
JavaScriptを用いた解説
JSの解説記事のサンプルコードのリポジトリ。ちょっと文法が古い。
ちなみに、JavaScriptの方を書いているのはDouglas Crockfordという人で、Pratt Parserの理論を用いてJSLintを作った人です。
苦労したこと
GoのコードをNimに書き換えていく作業はLexerのときよりかなり大変でした。
というのも、Nimにはインターフェースがなく、この型に対するエラーにはどう対処したら良いんだ？？というのが続出したからです。
Nimのフォーラムで質問したりもしたのですが、あまりにもそういった「どうにもならない状態」に出くわす頻度が高すぎるので、設計がおかしいのでは疑い始めました。
具体的には、本の中では、Identや式や文でインターフェースをわけていますが、Nimの方では一つの列挙型の中に定義し、一つのオブジェクトPNodeの中で分岐させて各構造体を作っています。
やはり、ある言語でコードを書くときは、その言語の思想を知り、それに則って書いていく必要があるんだなと感じました。
最後に
長い記事を読むのはあまり好きじゃないので、長い記事も書かないようにしているのですが、長くなってしまいました。
Parserの種類や、パーサージェネレータ、文脈自由文法など、構文解析一つとっても奥深いんだなとびっくりしました。
この辺の再帰を使う部分は関数型言語だと書きやすいっぽいので、OCamlかHaskellあたりで書いてみたいです。
Lexer、Parserとできたので、次はEvaluatorを作っていきます。
実際に数値を計算したりする部分です。
ちなみに本でいうとまだ半分くらいです。
先は長い・・。
参考